package hot100;

import org.junit.Test;

import java.util.*;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/9/12 9:12
 */
public class lc438找到字符串中所有字母异位词 {

    /*
      这个题 是做  lc 76 的基础， 两个题差不多
     */


    /*
      l 是被动 增加， r 是主动增加
     */














    // 未 优化版本 , 尽量 debug ，这样是最快的
    public List<Integer> solve(String s,String  p){
        int sa[] = new int[26], pa[] = new int[26];
        int pl = p.length(), sl = s.length();
        List<Integer> ans = new ArrayList<>();
        for(int i = 0;i < p.length();i++){
            pa[p.charAt(i) - 'a']++;
        }

        for (int l = 0, r = 0; r < sl; r++) {
            sa[s.charAt(r) - 'a']++;
            if (r - l + 1 >= pl){
                if(Arrays.equals(sa,pa)){
                    ans.add(l);
                }
                sa[s.charAt(l++) - 'a']--;

            }
        }
        return ans;
    }


    /*
     优化版本很巧妙
     主要是 sa 和 pa  数组的比较，
     判断 sa 是否 == pa， 只需要判断 sa 指定字符的出现的 个数是否 pa 相等
     只需要用一个 变量 count 计数 就可以了
     注意这里 countS 计数 的是什么，
     这里非常抽象， 不太容易解释， 多看题解吧
     */

    // 这个 题， 跟覆盖子串 还有一点区别， 要区分开， 但是可以写一个通用的做法
    //  这个题 优点绕的
    public List<Integer> solve2(String s,String  p){
        int sa[] = new int[26], pa[] = new int[26];
        int pl = p.length(), sl = s.length();
        List<Integer> ans = new ArrayList<>();
        for(int i = 0;i < p.length();i++){
            pa[p.charAt(i) - 'a']++;
        }
        long countP = Arrays.stream(pa).filter(x -> x != 0).count();
        long countS = 0;
        int l = 0, r = 0;
        while(r < sl){
            int c = s.charAt(r) - 'a';
            if(++sa[c] == pa[c]){
                countS++;
            }
            if(r - l + 1 > pl){//缩小窗口
                int c1 = s.charAt(l) - 'a';
                sa[c1]--;
                if(pa[c1] != 0 && sa[c1] + 1 == pa[c1]){ // 可以的没有问题， 先把窗口 变得合法然后再计算结果
                    countS--;
                }
                l++;
            }
            if(countP == countS){
                ans.add(l);
            }



            r++;
        }
        return ans;
    }






    @Test
    public void test(){
//        String s = "cbaebabacd", p = "abc";
//        List<Integer> solve = solve2(s, p);


        String s = "ababababab", p = "aab";
        List<Integer> solve = solve2(s, p);

//        long count = p.chars().filter(x -> x != 'a').count();
//        System.out.println(count);

        System.out.println(solve);

    }



}
